\documentclass[12pt]{article}
\usepackage{textcomp}
\usepackage{ucs}
\usepackage[utf8x]{inputenc}
\usepackage[T1]{fontenc}   
\usepackage[french]{babel} 
\usepackage{array}
\usepackage{amsmath}
\usepackage{supertabular}
\usepackage[pdftex]{graphicx}
\usepackage[paper=a4paper, left=2cm, right=2cm, top=2.5cm, bottom=2.5cm]{geometry}

\title{LSINF1121 : opérations de dérivation sur arbres binaires}
\author{Antoine Walsdorf, Robin Ballarini, Olivier Dekeyser, \\
Nikolas Darko, Julie Chatelain, Tristan Carion et Ludovic Fastré}
\date{\today}


\begin{document}
\maketitle

\newpage

\section*{Introduction}
	Dans le cadre de cette deuxième mission, nous avons dû réaliser un programme qui transforme une expression arithmétique en un arbre correspondant afin de la dériver.

\section{Hypothèses}
	Nous avons posé certaines contraintes sur les expressions analytiques que notre programme peut traiter: 
	\begin{itemize}
		\item les seuls nombres présents dans l'expression sont entiers
		\item les opérations possibles sont les quatre opérations arithmétiques, la puissance entière\footnote{sans variable analytique à l'exposant} et les fonctions sinus et cosinus
		\item la seule variable arithmétique est désignée par la lettre $x$
		\item les expressions sont fournies entièrement parenthésées	
	\end{itemize}
	
	Nous avons tiré parti de ces hypothèses afin de simplifier notre implémentation. Il s'agit notamment de simplifications au niveau du "parser". Le fait que les nombres soient entiers nous permet, lui, nous permet l'utilisation d'Integer et garantit une certaine précision au niveau de l'encodage des valeurs dans l'arbre.
	\paragraph{Négation}
		Nous avons, en plus, introduit le symbole ~ afin de permettre une négation. Cela permet de passer outre du fait que l'opérateur de soustraction occupe un nœud de l'arbre à lui tout seul et permet de mettre des entiers négatifs dans les nœuds.
		
\section{Choix de conception}
	 Lors de la conception de ce programme, nous avons dû faire plusieurs choix quant à la structure de notre programme et ce qu'il permettait.

\subsection{Classe LinkedRBinaryTree}
	Cette classe implémente les opérations de manipulation de base d'un arbre binaire ainsi que les opérations de dérivation.
	
	\paragraph{Types}
		Dans notre arbre, il est prévu que les valeurs des noeuds soient stockées sous la forme d'un String, Character ou Integer. Cela nous évite de faire certaines opérations de changement de type\footnote{de String vers Integer par exemple}. Bien que cela semble relativement mineur, cela pourrait être utile pour l'implémentation d'une future fonctionnalité de simplification par exemple. Nous avons donc permis qu'un arbre puisse contenir une valeur d'un type différent que ses sous-arbres.
		
	\paragraph{Dérivation}
		Nos méthodes servant à la dérivation sont structurées comme suit : 
		\begin{itemize}
			\item Une méthode centrale (public) qui choisit l'opération de dérivation à effectuer en fonction de la valeur se trouvant dans la racine
			\item Des méthodes spécifiques à chaque opération arithmétique ou fonction. Ces méthodes sont privées et uniquement appelées via la méthode centrale
		\end{itemize}
		
		L'avantage de cette approche est que, si nous voulons rajouter une nouvelle fonction à gérer, il nous suffit de rajouter la méthode spécifique correspondante et de modifier quelques lignes de la méthode centrale pour qu'elle soit prise en compte\footnote{Il faudra aussi rajouter une clause "else if" et une sous fonction pour le Parser}.
		
\subsection{Classe IO}
	Afin de pouvoir lire plusieurs expressions arithmétiques les unes à la suite des autres, nous avons décidé que notre programme prendrait en argument un fichier qui contiendrait les expressions à dériver\footnote{avec un passage à la ligne entre chaque}. Cette classe contient les méthodes statiques utilisées. Notons que rajouter quelques méthodes afin de permettre l'écriture dans un fichier serait facile, à condition d'adapter la méthode main et les arguments d'entrée qu'elle accepte.

\subsection{Classe Node}
	Les instances de cette classe enveloppent les objets servant de valeurs aux nœuds. Cela nous garantit que, lors d'une requête pour obtenir un élément de l'arbre, nous le recevions comme un objet de type E déterminé à la création de l'arbre\footnote{Et non comme une instance de Object}.
	
	Cette classe implémente l'interface position se trouvant dans [DSAJ-5].
	
\subsection{Classe Parser}
	Cette classe contient la méthode statique "parser" qui reçoit la chaîne de caractère passée en argument au programme et retourne son équivalent sous forme d'arbre binaire\footnote{Instance de LinkedRBinaryTree}. Cette fonctionnalité du programme est organisée de manière similaire à celle utilisée pour les méthodes de dérivation\footnote{voir plus haut}. De nouveau, cela permet de facilement rajouter de nouvelles opérations, fonctions ou même une autre variable analytique.
	
	Plus en détail, nous stockons les différents éléments de la chaîne de caractère dans des piles : une pour les opérateurs et une pour les opérandes\footnote{aussi appelée "pile des valeurs"}. Au début, tous ces éléments sont sous la forme d'arbres complètement disjoints et nous allons petit à petit les attacher les uns aux autres jusqu'à ce qu'il ne reste qu'un seul arbre : le résultat.
	
	Notons que c'est ici que nous faisons usage de la plupart des hypothèses posées. La plus importante étant que nous nous servons des parenthèses fermantes afin de réaliser des opérations sur les deux piles. Plus précisément, on récupère un opérateur, ses opérandes et on les attache sous forme d'un seul arbre avant le remettre le résultat dans la pile des valeurs.

\subsection{Classe Main}
	Cette classe se limite ici à une boucle sur les différentes expressions dans le fichier d'entrée.
	A chaque itération, on lit une expression, la transforme en arbre et on finit par la dériver. Le résultat est ensuite affiché sur la sortie standard.
	
\section{Limite de notre implémentation}
	\begin{itemize}
		\item Les expressions ne sont pas simplifiées après (ou même avant) dérivation\footnote{on pourrait néanmoins corriger ce point facilement : en appelant une méthode de simplification juste avant d'afficher le résultat}.
		\item Les expressions qui ne sont pas complètement parenthésées ne seront pas parsées correctement et cela est difficilement corrigeable sans changer complètement de "Parser"
		\item Théoriquement, les arbres LinkedRBinaryTree peuvent contenir des objets de n'importe quel type.
		\item Les nombres décimaux ne sont pas reconnus : cela pourrait causer des problèmes de simplification avec certaines fonctions si la simplification était implémentée.
		\item Éventuelles erreurs dues à la lecture du fichier.
	\end{itemize}

\end{document}